/*
 * @lc app=leetcode.cn id=20 lang=cpp
 *
 * [20] 有效的括号
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
   public:
    bool isValid(string s) {
        bool result = true;
        stack<char> char_stack;

        for (char c : s) {
            // 遇到左部，入栈
            if (c == '(' || c == '[' || c == '{') {
                char_stack.push(c);
            }

            // 遇到右部
            if (c == ')' || c == ']' || c == '}') {
                // 栈为空，错误
                if (char_stack.empty()) {
                    result = false;
                    break;
                }
                
                // 栈顶元素不匹配，错误
                if ((c == ')' && char_stack.top() == '(') ||
                    (c == ']' && char_stack.top() == '[') ||
                    (c == '}' && char_stack.top() == '{')) {
                    char_stack.pop();
                } else {
                    result = false;
                    break;
                }
            }            
        }

        // 有剩余的左部没有匹配，错误
        if (!char_stack.empty()) {
            result = false;
        }

        return result;
    }
};
// @lc code=end
